//
// Created by Administrator on 2021/5/29.
//
#include <vector>
#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *bstFromPreorder(vector<int> &preorder) {
        //给的是BST 有大小顺序
        //一个节点后面，直到比该节点孩子大的一段为左子树
        // 比该节点大的一段为右子树
        return helper(preorder, 0, preorder.size());
    }

    TreeNode *helper(vector<int> &v, int left, int right) {
        if (left >= right) return nullptr;
        auto node = new TreeNode(v[left]);
        int i = left;
        for (; i < right; ++i) { // 二分可能更快点
            if (v[i] > v[left])break;
        }
        node->left = helper(v, left + 1, i);
        node->right = helper(v, i, right);
        return node;
    }

    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) return;
        res.push_back(root->val);
        preorder(root->left, res); // 对左子节点递归调用
        preorder(root->right, res); // 对右子节点递归调用
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res; // 结果向量
        preorder(root, res);
        return res;
    }
};

int main() {
    vector<int> v{8, 5, 1, 7, 10, 12};
    Solution sol;
    auto ans = sol.bstFromPreorder(v);
    auto vv = sol.preorderTraversal(ans);
    for (auto &x:vv) cout << x << endl;
    return 0;
}